Tools for Modeling Validation Process:
The Dark Side of LP
The Dark Side of LP
To search the site, try Edit | Find in page [Ctrl + f]. Enter a word or phrase in the dialogue box, e.g. "parameter " or "linear " If the first appearance of the word/phrase is not what you are looking for, try Find Next.
MENU
- Introduction
- Unboundedness
- Multiple Optimal Solutions (Innumerable optimal solutions)
- No Solution (Infeasible LP)
- Degeneracy
- Degeneracy and the Dual (shadow) Prices
- Shadow Price Might Have Wrong Sign
- Redundancy Among the Constraints
- Identification of Unbounded Feasible Regions
- LP with no Vertex
- LP With Unbounded, and Multiple Bounded Optimal Solutions
- On the Basic and Nonbasic Decision Variables
- LP Without Any Interior, and Boundary Solutions
- Optimal Solution Generated by One LP Package Is Not Obtainable by the Other
- Does the Optimal Simplex Tableau Give the Dual Solution?
- Solution to an Integer LP May Not Be One of the Integer Vertices
- Conversion to the Standard Form May Distort the Feasible Region
- Removal of Equality Constraints by Substitution May Change the Problem
- Misinterpretation of the Shadow Price
- Is the Shadow Price Always Nonnegative?
- Alternative Shadow Prices
- The Cost Sensitivity Range by Grapical Method
- More-for-less & Less-for-more Situations
- JavaScript E-labs
Companion Sites:
- Linear Optimization Solvers to Download
- Success Science
- Leadership Decision Making
- Linear Programming (LP) and Goal-Seeking Strategy
- Artificial-variable Free LP Solution Algorithms
- Integer Optimization and the Network Models
- The Classical Simplex Method
- Zero-Sum Games with Applications
- Computer-assisted Learning Concepts and Techniques
- Linear Algebra and LP Connections
- From Linear to Nonlinear Optimization with Business Applications
- Sensitivity Region for LP Models
- Zero Sagas in Four Dimensions
- Probabilistic Modeling
- Systems Simulation
- Business Keywords and Phrases
- Compendium of Web Site Review
- Collection of JavaScript E-labs Learning Objects
- Decision Science Resources
Introduction
Potential problems exist which affect any linear programming application. Optimal solution may be infeasible or unbounded, or there may be multiple solutions. Degeneracy may also occur. The following figure presents a classification of LP for modeling validation process:
A Classification of Linear Programs' Solutions for Modeling Validation Process
These and other pitfalls are not of much deficiencies of linear programming as they are situations of which the decision maker should be cognizant. What can go wrong in the process of building an LP model?
Problems with LP Packages: Most LP software solvers have difficulties in recognizing the dark side of LP and/or giving any suggestions as remedies. Apply the following numerical problems to the WinQSB and discover and then report what you get as output.
Unboundedness
Identification: In the Simplex Solution Algorithm, if introducing column j and all aij in that column are less than or equal to zero, or the column ratio (C/R) cannot be performed. See also, the Degeneracy case.For example, consider the following problem:
Max Y1
subject to:
Y1 + Y2 -2T = 0
Y1 -Y2 = 2
all decision variables ³ 0.
Following the simplex iterations, we reach to the following table:
| BVS | Y1 | Y2 | T | RHS | |
|---|---|---|---|---|---|
| T | 0 | -1 | 1 | 1 | |
| Y1 | 1 | -1 | 0 | 2 | |
| Cj | 0 | 1 |
Although the variable Y2 should come in as a basic variable, all the elements in this column are less than zero. Therefore, the LP problem is unbounded.
Learn that an unbounded Optimal solution means having a closed unbounded feasible region, however, the inverse of this statement may not be correct. An unbound optimal solution means the constraints do not limit the optimal solution and the feasible region effectively extends to infinity.
Resolution: In real life, this is very rare. Check the formulation of the constraints, one or more constraints are missing. Check also the constraints for any mis-specification in the direction of inequality constraints, and numerical errors.
Sensitivity Analysis is not applicable.
The WinQSB and Lindo state that the problem is unbounded.
Unboundedness Feasible Region: As mentioned above, know that unbounded solution case required unbounded feasible region. The reverse of this statement may not be correct. For example the following LP problem has unbounded feasible region, however solution is bounded:
Max -4X1 -2X2
subject to:
X1 ³ 4
X2 £ 2
all decision variables ³ 0.
The optimal soution is X1 = 4, and X2 = 0.
Multiple Optimal Solutions (Innumerable optimal solutions)
Identification: In the simplex final tableau, if the row Cj (the last row in the tableau) is zero for one or more of the non-basic variables, then we may have more than one optimal solutions (therefore infinitely many optimal solution). To find all the other optimal corner point (if any), pivot on each of non-basic columns with zero Cj, one-by-one.The necessary condition for the existence of LP multiple solutions: If the total number of zeros in the Reduced Cost together with number of zeros in the Shadow Price columns exceeds the number of constraints, then you might have multiple solutions.
Example: The following problem has many optimal solutions:
Max 6X1 + 4X2
subject to:
X1 + 2X2 £ 16
3X1 + 2X2 £ 24
all decision variables ³ 0.
If you run the above problem on say WinQSB or Lindo you will find four zeros. However, you must notice that this is only a Necessary condition and not a Sufficient one, as for the above numerical example. Unfortunately, the QSB uses this necessary condition. Therefore, sometimes it gives Wrong messages.
Using your QSB computer package, you will get the following two solutions, (X1 = 8, X2 = 0) and (X1 = 4, X2 = 6). Notice that, the existence of multiple solutions means we have innumerable optimal solutions (Not just two).
Whenever, there are more than one vertices which are optimal, we can always generate all other optimal solutions by the "linear combination" of coordinates of all optimal vertices. For example, for the above problem, based on the two solutions obtained by QSB, all the following solutions are indeed optimal:
X1 = 8a + (1 - a)4 = 4 + 4a, X2 = 0a + (1- a)6 = 6 - a, for all 0 £ a £ 1.
Resolution: Check the coefficients in the objective function and the constraint. There could have been rounding errors.
Sensitivity Analysis is Not applicable. That is, The sensitivity analysis based on one optimal solution may not be valid for the others.
Warnings on Using Software Packages: Unfortunately, Lindo, does not provide any direct warnings about the existence of multiple solution. The WinQSB states that alternative optimal solutions have been found. However, such an statement could be misleading. For example, the following problem has a unique solution, the WinQSB states that there are multiple solution!
Max 30X1 - 4X2
S.T. 5X1 - X2 £ 30
X1 £ 5
X1 ³ 0
X2 is unrestricted.
The only solution is X1 = 5, X2 = -5 with the optimal value of 170.
For the following problem, the WinQSB produces 4 distinct multiple solutions:
Minimize X1 + X2 + 2X3
subject to:
X1 + X2 + X3 ³ 10
X1 + X2 + 2X3 ³ 13
X1, X2 are non-negative.
The set of all optimal solutions for this problem constitutes a half-plane. That is, all the optimal solutions are on the plane X1 + X2 + 2X3 = 13, such that X1 + X2 + X3 ³ 10, X1 ³ 0, X2 ³ 1, and X3 ³ 0.
Reference:
Appa G., On the uniqueness of solutions to linear programs, Journal of the Operational Research Society, 53(10), 1127-1132, 2002.
Steinberg D., and D. Aucamp, On ranging cost coefficients in dual degenerate linear programming problems, Decision Sciences, 14(3), 440-441, 1983.
No Solution (Infeasible LP)
An infeasible solution means the constraints are too limiting and have left no feasible region.For example the following problem has no solution:
Max 5X1 + 3X2
subject to:
4X1 + 2X2 £ 8
X1 ³ 4
X2 ³ 6.
Identification: If you cannot bring in any variable while maintaining feasibility (i.e. RHS values remaining non-negative).
Resolution: Check the constraints for any mis-specification in the direction of inequality constraints, and numerical errors. If no error exists, then there are conflict of interests. This must be resolved by finding the IIS (see the Note below) and then re-formulating the model.
Sensitivity Analysis: Not applicable.
Note: Most commercial packages such as CPLEX and LINDO have a feature called IIS (Irreducible Infeasible Subset) i.e., the minimal set of constraints one needs to remove from the problem in order to make it feasible. This set of constraints is infeasible, but an proper subset of an IIS is feasible. Hence all of the constraints in the IIS contribute to the infeasibility. This means that one must remove or modify at least one of the constraints in the IIS in order to render the model feasible. Therefore, finding an IIS, then, simply helps to focus the diagnostic effort. There may be several different IIS's in the model, and that a single error may present it itself via different IISs. Hence the you must repair the model as follows:
Step 1: find an IIS,
Step 2: repair the infeasibility in the IIS, and
Step 3: check whether the entire model is feasible yet; if not, go to Step 1.
In Automatic Schedule Generation Packages, for example, the total elimination of inconsistencies from the initial input data is a hard task. Therefore, some packages are equipped with an interface module that acts like a debugger. This will eliminate many of surface-level infeasibility during the first run. Several more runs might be needed to eliminate deeper infeasibility. As an alternative approach, infeasibility problem might be handled as an optimization problem, with the objective of minimizing the (possibly weighted) number of constraint violations. When no solution satisfies all the constraints, a near solution is found. This near solution may highlight the conflicting input data that need addressing.
A lesson learned for decision making: You may have heard that "If there is a will, then there must be a way". In fact the advice should be in the opposite order, i.e. "If there is a way, then there might be a will". It is right because the feasible region might be empty, and one might ignores one or some constraints, and then being in a big trouble, e.g., willing beyond ones' ability.
Degeneracy
Consider an LP with n decision variables, a degenerate vertex is the one through which more than n hyper-planes pass. For eaxample, 3 or more lines in a 2-dimensional space LP problem. On such a vertex, a method such as simplex, can switch from one representation (with n hyper-planes) to another one and may even end up cycling back to the first one and repeating this "cycle". Now adding small quantities to, say, the right-hand sides of the constraints, moves the corresponding hyper-planes slightly and "perturbs away" the vertex. Instead, there will be several close-by vertices where typically just n hyper-planes meet. Now, the method can go from one to the other (improving the objective function each time) and leave this degenerate area. Then, the perturbation can be turned off again in modern computer implementation of simplex methods and its many variations.A corner point in a n-dimensional decision variables problem is called a degenerate corner point if more than n constraints become binding (i.e. active) at that corner point. That is, whenever some corner points osculate. For example, in a 2-dimensional problem, a corner point is degenerate if at that corner point 3 or more constraints become equalities.
For example, consider the following two dimensional problem:
Max X1 + X2
subject to:
X1 £ 1
X2 £ 1
X1 + X2 £ 2
all decision variables ³ 0.
The optimal solution is X1 = 1, and X2 = 1, at which all three constraints are binding.
Whenever the optimal solution is degenerate, then you will have multiple shadow prices. For the above problem, the two sets of shadow prices are (1, 1, 0) and (0, 0, 1) as you may verify by constructing and solving its dual problem.
Identification: If there are at least two equal and smallest column ratios (bi/aij) while applying the simplex method then the solution is degenerate arbitrarily choose an outgoing variable.
In rare cases, degeneracy may cause cycling, as in the following problem:
Max 6X1 + 3X2
subject to:
X1 £ 1
X2 £ 1
X1 - X2 £ 1
-X1 + X2 £ 1
all decision variables ³ 0.
Both Lindo and WinQSB take 3 iterations to solve this simple degenerate problem.
Resolution: Add to the RHS value a small number, say, 0.001. This may resolve the problem.
Sensitivity Analysis: The sensitivity analysis may Not be valid and you may have Alternative Shadow Prices.
The following problem and its dual, are both degenerate:
Min X2
subject to:
X2 - 2X3 + X4 = 1
X1 + 2X2 - X3 = 0
X1 + X2 + 3X3 = 2
all decision variables ³ 0.
Further Readings:
Aucamp D., and D. Steinberg, The computation of shadow price in linear programming, Journal of Operational Research Society, 33, 557-565, 1982.
Evans J., and N. Baker, Degeneracy and the (mis)interpretation of sensitivity analysis in linear programming, Decision Sciences, 13, 348-354, 1982.
Gass S., and S. Vinjamuri, Cycling in linear programming problems, Computers & Operations Research, 31, 303-311, 2004.
Jansen B., Sensitivity analysis in linear programming: just be careful!, European Journal of Operational Research, 101, 1997, 15-28.
The Cost Sensitivity Range by Grapical Method
It is a commonly held belief that one can compute the cost sensitivity range by bracketing the (perturbed) slope of the (iso-value) objective function by the slopes of the two lines resulting from the binding constraints. This graphical slope-based method to compute the sensitivity ranges is described in popular textbooks, such as Anderson et al., (2007), Lawrence and Pasternack (2002), and Taylor (2006).Unfortunately these are misleading. Warning should have been given that their approach is not general and works if and only if the coefficients do not change sign.
In an LP with 2 variables and inequality constraints, suppose we have a unique, non-degenerate optimum at the intersection of two lines, as shown in the following figure. Then, the range of objective coefficients for which this solution remains optimal is given by the slopes of the two lines.
The following is a counterexample. It points out that one must be careful to state that the coefficients do not change sign.
Counterexample: Maximixe 5X1 + 3X2
X1 + X2 £ 2,
X1 - X2 £ 0,
X1 ³ 0, X2 ³ 0.
Further Readings:
Lawrence J., Jr., and B. Pasternack, Applied Management Science: Modeling, Spreadsheet Analysis, and Communication for Decision Making, John Wiley and Sons, 2002.
Anderson D., Sweeney D., and Williams T., An Introduction to Management Science, West Publisher, 2007.
Taylor III, B., Introduction to Management Science, Prentice Hall, 2006.
Degeneracy and the Dual (shadow) Prices
When the optimal solution is primal degenerate, then the usual sensitivity analyses does not provide complete information in the degenerate case., that is, the information one obtains from most LP packages are a subset of the true sensitivity intervals. There are more advanced sensitivity analysis approaches to cope with this problem; however they are computationally much more involved than the usual sensitivity analysis.For example, considering the following LP with a degenerate optimum solution:
Max 3X1 + 9X2
subject to:
X1 + 4X2 £ 8
X1 + 2X2 £ 4
X1, X2 ³ 0
When solving by the simplex method: Enter X2 and break the tie for the leaving variable in favor of the first row. The dual (shadow) price for RHS1 is 1.5 valid in the range [4, 8], and the dual price for RHS2 is 1.5 valid in the range [4, 8]
Next, re-solve the problem changing the order of R1 and R2 and also breaking the tie for the leaving variable in favor of the second row. The dual price for RHS1 is 0 valid in the range [8, ¥), the dual prince for RHS2 is 4.5 valid in the range [0, 4]
This shows that the resulting values of the dual prices could depend on how different solvers deal with the ties. The main question is: If this is an allocation model, which of the two sets of dual solutions apply? In this simple example, it seems that the first set of dual values yields more useful information because it says that RHS2 can be increased by up to 4 units with each unit increasing the optimal value by 1.5. The second set, on the other hand, does not reveal any advantage in increasing RHS1 or RHS2.
In both cases, the first range represents reduction in resource and hence a unit reduction in z by 1.5 and 4.5, respectively. The second range represents an increase in resource with no effect on optimal value in RHS1 and a unit increase of 1.5 in RHS2. These results make sense; however, the procedure of "enumerating" alternative degenerate optima is out of the question for practical problems.
Enumerating multiple optima is in general NP-hard, but you don't need all the optima to get the full shadow price picture, at least for changes to individual constraints. If degeneracy causes a "one-sided" range (current RHS of the constraint is an
Further Readings:
Roos C., T. Terlaky, and J. Vial, Theory and Algorithms for Linear Optimization: An Interior Point Approach, John Wiley & Sons, 1997. Chapter 19.
Shadow Prices Might Have Wrong Sign
Some LP software packages do not obey strict duality for both maximization and minimization. Therefore one has to take that into account adjust the signs accordingly. This can be done by changing the RHS by “small” amount and finding the new optimal value, then using the definition of shadow price as the rate of change in the optimal value with respect to the change in the RHS.For example, considering the following LP with a unique optimum solution:
Minimize 18X1 + 10X2
Subject to:
12X1 + 10X2 ³ 120000
10X1 + 15X2 £ 150000
X1, X2 ³ 0
Running this problem by LINDO, the final report gives the shadow prices U1 = -2.125, and U2 = 0.75, while the correct ones are U1 = 2.125, and U1 = - 0.75. This unfortunate error is not limited to LINDO, for example the QM: Quantitative Methods for Windows, produces the same results.
Further Readings:
Arsham H., Foundation of Linear Programming: A Managerial Perspective From Solving System of Inequalities to Software Implementation, International Journal of Strategic Decision Sciences, 3(3), 40-60, 2012.
Arsham H., An Interior Boundary Pivotal Solution Algorithm for Linear Programs with the Optimal Solution-based Sensitivity Region,International Journal of Mathematics in Operational Research, 4(4), 302-330, 2012.
Arsham H., A Validation and Verification Tool for Optimization Solvers,
Journal of Information & Optimization Sciences, 29(1), 57-80, 2008.
Redundancy Among the Constraints
Redundancy means some constraints are not needed as there are other more severe ones. For a simple case of an LP with redundant constraint, consider the following numerical example:Maximize 5X1 + 6X2
subject to: 3X1 + 6X2 £ 8, 6X1 + 4X2 £ 24, and both X1, X2 ³ 0.
Identification: At least a row in the tableau has all elements including the RHS value equal to zero.
Resolution: Delete such rows and proceed. However, the redundancy of constrains is not absolute but relative. In addition, the "minimally" of a set of constraints, i.e., there are no redundant ones, for describing a feasible region, does not necessarily imply that the number of constraints is the smallest.
Sensitivity Analysis: The RHS sensitivity analysis may not be valid, and for the redundant constraints are not available, moreover you may have Alternative Shadow Prices. For example, in almost all Networks Models one of the constraints is always redundant, therefore the computer software (such as QSB Nets Module) results on sensitivity analysis for these types of problems may not be valid.
Identification of Unbounded Feasible Region
Much care must be taken in the process of building a mathematical model prior to using any solution algorithm. Potential problems may exist which affect any optimization solution algorithm. The feasible region could be unbounded, although in real life it is rare to have an unbounded feasible region.
Given the following standard-form feasible region F = { X: A X = b, X ³ 0}, where A is a given m by n matrix and b is a m-vector, we are interested to check if the feasible region is unbounded or not.
Given the set F is nonempty then F is unbounded if and only if the following LP problem has a nonzero vector Y as its solution:
Maximize S Yi
Subject to: A Y = 0, 0 £ Yi £ 1, for all i’s
Proof follows from Farkas' lemma. Moreover, the optimal solution Y* will be an unbounded direction.
Notice that solving a simple LP with a dummy objective function, such as:
Minimize X1
Subject to: A X = b, X ³ 0
can check the condition that F must be nonempty, if this simple LP has a bounded solution.
We now employ a numerical example to illustrate the above procedure.
Consider the following nonempty feasible region:
| 5X1 | - | X2 | £ | 30 | |
| X1 | £ | 5 | |||
| X1 | ³ | 0 | , | X2 | is unrestricted in sign |
To convert the feasible region to the standard form can be achieved by substituting X2 – X3 for X2, and introducing slack variables X4, and X5 for the two £ constraints, respectively. The standard-form of the region is:
| 5X1 | - | X2 | + | X3 | + | X4 | = | 30 |
| X1 | + | X5 | = | 5 |
All variable are nonnegative.
The above feasible region is unbounded if and only if the following LP has a non-zero Y* as its optimal solution:
Maximize Y1 + Y2 + Y3 + Y4 + Y5
| 5Y1 | - | Y2 | + | Y3 | + | Y4 | = | 0 |
| Y1 | + | Y5 | = | 0 | ||||
| Yi | £ | 1 | , | for all i’s, |
and all variable are nonnegative.
The optimal solution is Y* = [0, 1, 1, 0, 0] which is nonzero. Therefore, the feasible region is indeed an unbounded one.
LP with no Vertex
The following LP has no vertex:Maximize X1 + X2
subject to: X1 + X2 £ 5, X1, X2 unrestricted.
This problem has a closed unbounded feasible region with no vertex. However all multiple solutions are the points on the line X1 + X2 = 5.
The Standard Form: Now by converting the inequality into equality with slack variable S1 and restricting the variables by X1 - y, and X2 -y, we have the following basic solutions:
| X1 | X2 | y | S1 | X1+X2 | |
| __________________________ | |||||
| 0 | 0 | 0 | -5 | not feasible | |
| 0 | 0 | -5/2 | 0 | not feasible | |
| 0 | 5 | 0 | 0 | 5 | |
| 5 | 0 | 0 | 0 | 5 | |
This gives two basic feasible solution with equal objective values. It indicates that, there are multiple solutions, however, the original feasible region is distorted!
For this problem, the WinQSB produces two distinct optimal solutions: (X1 = 5, X2 = 0), and (X1 = 0, X2 = 5) which are not vertices. It is noteworthy that, not only any convex combination of these two points is optimal, but also the points beyond them are optimal.
LP with Unbounded, and Multiple Bounded Optimal Solutions
Consider th following LP problem:Maximize X1 + X2
subject to: X1 + X2 = 5, both X1, and X2 are unrestricted in sign.
This problem has a closed unbounded feasible region. The optimal solutions are multiple, both bounded and unbounded which are all the points on the line X1 + X2 = 5.
On the Basic and Nonbasic Decision Variables
In performing simplex iterations, is it true that "if a decision variable become a basic variable, then it remains basic". No, not always. A nonbasic decision variable may becomes a basic variable in a simplex iteration, and a latter iteration it becomes nonbasic again. Consider the following problem:
Maximize 5X1 + 6X2
subject to: 3X1 + 6X2 £ 8, 6X1 + 4X2 £ 24, and both X1, X2 ³ 0.
Applying the Simplex method in solving this problem, the decision variable X2 becomes a basic variable after the first simplex iteration. However, in the second iteration, the decision variable X1 replaces X2 as a new basic variable. The second iteration, for this problem, provides also the optimal solution. Notice that, one of the constraint is a redundant constraint.
LP Without Any Interior, and Boundary Solutions
Consider the following problem:Maximize X1 + 2X2
subject to: X1 + X2 = 2, X1 - X2 = 0, X1³ 0, and X2 ³ 0.
The problem has a feasible region which is a single point (X1 = 1, X2 = 1), with optimal value of 3. Therefore, this problem has neither interior point nor any boundary point. It has only a vertex.
Optimal Solution Generated by One LP Package Is Not Obtainable by the Other
Solution obtained by one LP package may not be obtainable by the other. Consider the following numerical example:
Minimize X1 + X2 + 2X3
subject to:
X1 + X2 + X3 ³ 10
X1 + X2 + 2X3 ³ 13
X1, X2 unrestricted in sign
WinQSB: Using the WinQSB package, you will get the following multiple solutions A = (0, 7, 3) and B = (7, 0, 3). This suggests that all the points between these generated optimal solutions are also optimal. That is, all linear combinations of these two solutions are also optimal:
X1 = 0a + (1 - a)7 = 7 - 7a,
X2 = 7a + (1- a)0 = 7a,
X3 = 3a + (1- a)3 = 3,
for all 0 £ a £ 1.
However, notice that, both constraints are binding, therefore solutions are on the intersection of these two planes, which is a line. Moreover, any point on the whole line are optimal not restricted to points between A and B. In other words, any points on the intersection line (in parametric form):
X1 = t,
X2 = 7 - t,
X3 = 3,
are optimal, for all t, including when t is a big-M.
Therefore, this LP problem has no vertex, has multiple bounded solutions, and unbounded solutions.
Lindo: To run this problem on Lindo, we must first satisfy the non-negativity conditions by substituting for every unrestricted variable Xi = xi - y. The result is:
min x1 + x2 + 2x3 - 5y
subject to:
x1 + x2 + x3 - 3y ³ 10
x1 + x2 + 2x3 - 5y ³ 13
All variables are non-negative.
Running this problem on Lindo (or your WinQSB), we get x1 = 13 and all other variables are equal to zero. In terms of the original variables, this gives: X1= 13, X2 = 0, and X3 = 0. As you see, the solution obtained by Lindo is not obtainable by WinQSB package and vice versa. Clearly, the sensitivity results for this problem using either of the packages are not valid. The set of all optimal solutions is a half-plane, that is:
Max 10U1 + 13U2
subject to:
U1 + U2=1
U1 + U2=1
U1+2U2=2
all variables are non-negative.
Running the dual on Lindo (or your WinQSB), we get the U1 = 0, U2 = 1, with shadow prices (0, 13, 0) which is the solution of the primal obtained earlier by Lindo (or your WinQSB). However, deleting the first redundant constraint in the dual problem, we have:
Max 10U1 + 13U2
subject to:
U1 + U2=1
U1+2U2=2
all variables are non-negative.
Now by running this problem on Lindo (or your WinQSB), we get the U1 = 0, U2 = 1, with shadow prices (7, 3) which is the solution (0, 7, 3) of the primal problem obtained earlier by WinQSB. The other solution is not producible.
Using the WinQSB for the dual problem, we get the U1 = 0, U2 = 1, with shadow prices (0, 7, 3) which is one of the solutions for the primal obtained earlier by this software.
Does the Optimal Simplex Tableau Give the Dual Solution?
The usefulness of the final simplex tableau for managerial application comes from the fact that it contains all the information you need to perform the sensitivity analysis, as you will see latter in this course. However, optimal simplex tableau does not provide the solution to the dual problem by itself. The shadow prices are the solution to the dual problem.As you know by now, the shadow price could be positive, zero, or even negative, however, in the final simplex tableau, the last row must always be non-positive (as solution algorithms required). Therefore, we cannot simply read-off the shadow prices from the final tableau, before formulating the dual problem.
Numerical Example: Consider the following problem,
Maximize 3X1 + 5X2
Subject to:
X1 + 2X2 £ 50,
-X1 + X2 ³ 10,
X1 ³ 0, X2 ³ 0.
Introducing slack and surplus variables, S1 and S2 respectively, and following the Arificial-free Solution Algorithm steps, we get the following final simplex tableau:
| BVS | X1 | X2 | S1 | S2 | RHS | |
|---|---|---|---|---|---|---|
| X1 | 1 | 0 | 1/3 | 2/3 | 10 | |
| X2 | 0 | 1 | 1/3 | -1/3 | 20 | |
| Cj | 0 | 0 | 8/3 | 1/3 |
The shadow prices are not (8/3, 1/3). You see this, after constructing the dual problem which is:
Minimize 50Y1 + 10Y2
Subject to:
Y1 - Y2 ³ 3,
2Y1 + Y2 ³ 5,
Y1 ³ 0,
and Y2 £ 0.
Having the dual problem formulation, now you can read off correctly the shadow prices. Therefore, the shadow prices are Y1 = 8/3, and Y2 = -1/3. Again, when you construct the dual, of the problem, you see that, Y2 must be £ 0, in sign. That is why you take -1/3 instead of 1/3 for Y2, from the final simplex tableau.
Solution to an Integer LP May Not Be One of the Integer Vertices
Whenever there is integrality condition on some decision variable, then the optimal solution (if exists) might be located anywhere on the feasible region. It might be one of the vertices, could be on the boundary or even inside the feasible region.Consider the following integer linear program from Shenoy (1989):
Maximize 100X1 + 160X2
Subject to:
6X1 + 14X2 £ 42
7X1 + 7X2 £ 35
X1, X2 are non-negative integers.
For this small example, one may find all 14 feasible solutions directly from the feasible region, then using the objective function iso-value lines, the optimal solution is at point (X1 = 4, X2 = 1), with the optimal value of 560.
This solution is superior to (X1 = 5, X2 = 0) with objective function value of 500 given therein. Notice that the optimal solution in on the boundary line 7X1 + 7X2 = 35, but not a vertex as is found in the above reference.
Further Reading
Shenoy G.V., Linear Programming: Methods and Applications, John Wiley & Sons, 1989.
Conversion to the Standard Form May Distort the Feasible Region
Consider the following LP problem:Maximize X1 + X2
subject to: X1 + X2 £ 5, X1, X2 unrestricted.
This problem has a closed unbounded feasible region with no vertex. However all multiple solutions are the points on the line X1 + X2 = 5.
Now let's see what we get if we convert this problem into the standard form which is a requirement to initiate the Simplex Method.
The Standard Form: Now by converting the inequality into equality with slack variable S1 and restricting the variables by X1 - y, and X2 -y, we have the following standard form:
Maximize X1 + X2 -2y
subject to:
X1 + X2 -2y + S1 = 5, and all variables are restricted in sign.
The basic solutions are:
| X1 | X2 | y | S1 | X1+X2 | |
| _________________________ | |||||
| 0 | 0 | 0 | 5 | 0 | |
| 0 | 0 | -5/2 | 0 | not feasible | |
| 0 | 5 | 0 | 0 | 5 | |
| 5 | 0 | 0 | 0 | 5 | |
This gives optimal vertices. It indicates that, there are multiple solutions. However, the original feasible region is now distorted!, that is, we are Not able to produce all the solutions by using any convex combination of the two solutions (0, 5) and (5, 0).
To find all the solution for this problem, we need to know the following two definitions:
Ray: A ray is a half-line: {V + ah: a ³ 0}, where h is a non-zero vector contained in S. Point V is called the root, and it is said that the ray is rooted at V.
Extreme Ray: A extreme ray of a closed set S is a ray in S that cannot be expressed as a linear combination of other rays in S.
All the optimal points are located at either of two extreme rays both rooted at V = (0, 5), in the directions (1, -1), and (-1, 1):
(X1, X2) = (0, 5) + a1(1, -1) + a2(-1, 1) =
(a1 - a2, 5 - a1 + a2),
for all a1 ³ 0, and a2 ³ 0.
Instead of (0, 5) any point on the line can be used.
However, to represent all the points in the feasible region, we need an additional term:
(X1, X2) = (0, 5) + a1(-1,1) + a2(1,-1) + a3(-1,-1),
for all a1 ³ 0, a2 ³ 0, and a3 ³ 0.
The last term is necessary for all the point bellow the line. It comes from the fact that both variables are unrestricted in sign [in directions [(0, -1) and (-1, 0)].
General idea for parametric representation is that we start at a vertex. We move away from it in the feasible direction of every edge to the next feasible point. If such point exists (i.e., we have found another vertex). If not, the polyhedron is not constrained in that direction and it means that the direction is an extreme ray. Notice that, the polyhedron without vertex always contains a line (or hyper-plane). For such polyhedron we also have to add additional ray perpendicular to that line (or hyper-plane) IF the constraint is in the form of inequality ( ³, or £ as in the above example.
Further Reading
Chvatal, V., Linear Programming, W. H. Freeman and Company, New York (1983), Chapter 18.
Removal of Equality Constraints by Substitution May Change the Problem:
Whenever there are any equality constraints in any LP problem, there is a temptation to reduce the size of problem by removing the equality constraints by substitutions. The problem remains the same if one eliminates the unrestricted variable(s) by using any equality constraints (if possible). However, if there is no unrestricted variables one must remove the equality constraints by substitution, because it may create a totally different LP problem. Here is a counter example for removing an equality constraint:Max X1
Subject to:
X2 + X3 = -1
X1 - 2X2 + X3 £ 1
X1 + X2 £ 2
All variables are non-negative.
This problem is has no solution. However by substituting for, say X3 = -1 - X2 everywhere, the problem changes to:
Max X1
Subject to:
X1 - 3X2 £ 2
X1 + X2 £ 2
All variables are non-negative,
giving you the optimal solution (X1 = 2, X2 = 0), with optimal value of 2. Therefore, these two problems are Not equivalent.
However, you may ask: Under what conditions is it safe to eliminate an equality constraint by substitution? The answer is either under unrestricted variable, as mentioned earlier, or if all the coefficients of an equality constraint have the same sign as its RH, then it will be safe to eliminate any variable by substitution in order to reduce the number of variables and constraints.
Further Readings:
Arsham H., An Artificial-Free Simplex Algorithm for General LP Models, Mathematical and Computer Modelling, 25(1), 107-123, 1997.
Misinterpretation of the Shadow Price
The Shadow Price tells us how much the objective function will change if we change the right-hand side of the corresponding constraint. This is often called the "marginal value", "dual prices" or "dual value", for the constraint. Therefore, the shadow price may not be same as the "Market price".For each RHS constraint, the Shadow Price tells us exactly how much the objective function will change if we change the right-hand side of the corresponding constraint within the limits given in the sensitivity range on the RHS's.
Therefore, for each RHS value, the shadow price is the ratio of the change in the optimal value caused by any allowable increase or decrease in the RHS within the permissible change.
A Counterexample:
Consider the following LP:
Max X2
subject to:
X1 + X2 £ 2
2.5X1 + 4X2 £ 10
where both decision variables are non-negative.
This problem attains its optimal solution at (0, 2) with an optimal value of 2.
Suppose we wish to compute the shadow price of the first resource that is the RHS of the first constraint.
Changing the RHS of the first constraint by increasing it by one unit results in:
Max X2
subject to:
X1 + X2 £ 3
2.5X1 + 4X2 £ 10
where both decision variables are non-negative.
The new problem has the optimal solution (0, 2.5) with an optimal value of 2.5.
Therefore, it seems "as-if" the shadow price for this resource is 2.5 - 2 = 0.5. In fact the shadow price for this resource is 1, which can be found by constructing and solving the dual problem.
The reason for this error becomes evident if we notice that the allowable increase to maintain the validity of the shadow price of the first resource is 0.5. The increase by 1 is beyond the allowable change on the first RHS value.
Now suppose we change the same RHS value by, say + 0.1 which is permissible, then the optimal value for the new problem is 2.1. Therefore the shadow price is (2.1 -2) / 0.1 = 1. We must be a little careful when calculating shadow prices.
If you wish to compute the shadow price of a RHS when its sensitivity range is not available, you may obtain the optimal values for at least two perturbations. If the rate of change for both cases gives you the same values, then this rate is indeed the shadow price. As an example, suppose we perturb the RHS of the first constraint by +0.02 and -0.01. Resolving the problem after these changes using your LP solver, the optimal values are 2.02, and 1.09, respectively. Since the optimal value for the nominal problem (without any perturbation) is equal to 2, the rate of change for the two cases are: (2.02 - 2)/0.02 = 1, and (1.09 - 2)/(-0.01) = 1, respectively. Since these two rates are the same, we conclude that the shadow price for the RHS of the first constraint is indeed equal to 1.
Is the Shadow Price Always Nonnegative?
You may be wondering "Is the shadow price of a RHS value always nonnegative?" It all depends on the formulation of the primal and its dual. What is important to remember is that the shadow price of a given RHS is the rate of change in the optimal value with respect to change on that RHS, given the change is within the sensitivity limits of that RHS.Consider the following numerical example:
Max 3X1 + 5X2
Subject to:
X1 + 2X2 £ 50
-X1 + X2 ³ 10
X1, X2 are nonnegative.
We are interested in finding the shadow price of RHS2 = 10. The dual problem is:
Min 50U1 + 10U2
Subject to:
U1 - U2 ³ 3
2U1 + U2 £ 5
U1 ³ 0, while U2 £ 0
This can be verified by using your WinQSB software. The solution to the dual is U1 = 8/3, U2 = -1/3. Therefore, the shadow price for RHS2 = 10 is U2 = -1/3. That is, for every unit increase (decrease) in RHS2 value the optimal value for the primal problem decreases (increases) by 1/3, given the change in RHS2 is within its sensitivity limits.
For another version of the same primal problem, notice that the problem can be written equivalently by changing the direction of the second inequality constraint:
Max 3X1 + 5X2
Subject to:
X1 + 2X2 £ 50
X1 - X2 £ -10
X1, X2 are nonnegative.
The dual problem for this primal problem is now:
Min 50Y1 - 10Y2
Subject to:
Y1 + Y2 ³ 3
2Y1- Y2 £ 5
Both Y1 and Y2 are nonnegative.
Again, the dual formulation can be verified by using your WinQSB software. The solution to this dual problem is Y1 = 8/3 and Y2 = 1/3. Therefore, the shadow price for RHS2 = -10 is Y2 = 1/3. That is for every unit increase (decrease) in RHS2 value the optimal value for the primal problem increase (decreases) by 1/3, given the change in RHS2 is within its sensitivity limits.
As you have already noticed both dual problems are the same when substituting U1 = Y1, and U2 = -Y2. This means the shadow price obtained for RHS2 = 10, and RHS2 = -10 have the same value with the opposite sign (as expected). Therefore, the sign of the shadow price depends on how you formulate the dual, although the meaning and its interpretation are always the same.
Also visit the
More-for-less & Less-for-more Situations.
Alternative Shadow Prices
Suppose we have an LP and it has the unique optimal solution. Is it possible to have more than one set of dual prices?Yes, it is possible. Consider the following problem:
Min 16X1 + 24X2
subject to:
X1 + 3X2 ³ 6
2X1 + 2X2 ³ 4
all decision variables ³ 0.
Its dual is:
Max 6U1 + 4U2
subject to:
U1 + 2U2 £ 16
3U1 + 2U2 £ 24
all decision variables ³ 0,
This dual has many alternative solutions such as, (U1 = 8, U2 = 0) and (U1 = 4, U2 = 6). All the convex combinations of these two vertices are also solutions.
There are general cases for which the shadow prices are not unique. As in the above example, whenever there is redundancy among the constraints, or if the optimal solution is "degenerate", there might be more than one set of dual prices. In general, the linear independent constraints are a sufficient condition for uniqueness of shadow prices.
Consider the following LP problem with a redundant constraint:
Max 10X1 + 13X2
subject to:
X1 + X2 = 1
X1 + X2 = 1
X1+2X2 = 2
and all variables are non-negative.
Running the dual on Lindo (or your WinQSB ) results in X1 = 0, X2 = 1, with shadow prices (0, 13, 0).
Using the WinQSB for this problem, we get the X1 = 0, X2 = 1 with different shadow prices (0, 7, 3).
In the case of redundancy, the shadow price obtained by one LP package may not be obtained by other.
Further Readings:
Arsham H., Distribution-Routes Stability Analysis of the Transportation Problem, Optimization, 43, 47-72, 1998.
Clarke F., Optimization and Nonsmooth Analysis, John Wiley & Sons, 1983.
More-for-less & Less-for-more Situations
Consider the following production LP problem:
Maximize X1 + 3X2 + 2X3
subject to: X1 + 2X2 + X3 = 4, 3X1 + X2 + 2X3 = 9, all Xi are non-negative.
The total labors are 4 and 9. The optimal value for this problem is $7.
Now, if you change the second available labor from 9 to 12, the optimal value would be $4. That is, you've worked more hours for less profit.
This situation arises frequently and is known as "The More-for-less Paradox". The resource number 2 has a negative shadow price!
To find out the best number of hours, you must work to maximize your income by solving the following parametric LP:
Maximize X1 + 3X2 + 2X3
subject to: X1 + 2X2 + X3 = 4, 3X1 + X2 + 2X3 = L , L, and all Xi are non-negative.
Using LINDO (or your WinQSB) we must solve
Maximize X1 + 3X2 + 2X3
subject to: X1 + 2X2 + X3 = 4, 3X1 + X2 + 2X3 - L = 0.
The optimal L is 8 hours, and the optimal value is $8!
The necessary and sufficient condition for the existence of the more-for-less/less-for-more situation is to have equality constraint(s) with negative shadow price(s) for the RHS values.
For more on this and other paradoxes visit:
Counterexamples and Explanations for LP Myths
For relevant references to sensitivity analysis visitBibliography for Optimization with Sensitivity Analysis
The Copyright Statement: The fair use, according to the 1996 Fair Use Guidelines for Educational Multimedia, of materials presented on this Web site is permitted for non-commercial and classroom purposes only.
This site may be mirrored intact (including these notices), on any server with public access, and linked to other Web pages. All files are available at
http://home.ubalt.edu/ntsbarsh/Business-stat for mirroring.
Kindly e-mail me your comments, suggestions, and concerns. Thank you.
This site was launched on 2/25/1994, and its intellectual materials have been thoroughly revised on a yearly basis. The current version is the 8th Edition. All external links are checked once a month.